#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
@File    : dfs.py
@Time    : 2023/01/29 21:40:40
@Author  : 郭瑞强
@Contact : sunraing@126.com
@Version : 0.1
@License : BSD 3-Clause License
@Desc    : 通用深度优先搜索
"""
from .vertex import Vertex
from .graph import Graph
from .state import State


class DFSGraph(Graph):
    def __init__(self) -> None:
        super().__init__()
        self.time = 0
        self.dfs_roots: list[Vertex] = []

    def dfs(self):
        # 初始所有节点为未访问状态
        for vert in self:
            vert.set_state(State.unreached)
            vert.set_pred(None)
            self.dfs_roots = []

        # 逐节点开始遍历，形成深度优先子树
        for vert in self:
            if vert.get_state() == State.unreached:
                self.dfs_roots.append(vert)
                self.dfs_visit(vert)

    def dfs_visit(self, start_vert: Vertex):
        start_vert.set_state(State.reached)
        self.time += 1
        start_vert.set_discover(self.time)

        for next_vert in start_vert.get_connections():
            if next_vert.get_state() == State.unreached:
                next_vert.set_pred(start_vert)
                self.dfs_visit(next_vert)

        start_vert.set_state(State.explored)
        self.time += 1
        start_vert.set_explored(self.time)

    def __iter__(self):
        return iter(self.dfs_roots)
